Algorithms for group isomorphism via group extensions and cohomology

摘要

The isomorphism problem for finite groups of order n (GpI) has long beenknown to be solvable in $n^{\log n+O(1)}$ time, but only recently werepolynomial-time algorithms designed for several interesting group classes.Inspired by recent progress, we revisit the strategy for GpI via the extensiontheory of groups. The extension theory describes how a normal subgroup N is related to G/N viaG, and this naturally leads to a divide-and-conquer strategy that splits GpIinto two subproblems: one regarding group actions on other groups, and oneregarding group cohomology. When the normal subgroup N is abelian, thisstrategy is well-known. Our first contribution is to extend this strategy tohandle the case when N is not necessarily abelian. This allows us to provide aunified explanation of all recent polynomial-time algorithms for special groupclasses. Guided by this strategy, to make further progress on GpI, we considercentral-radical groups, proposed in Babai et al. (SODA 2011): the class ofgroups such that G mod its center has no abelian normal subgroups. This classis a natural extension of the group class considered by Babai et al. (ICALP2012), namely those groups with no abelian normal subgroups. Following theabove strategy, we solve GpI in $n^{O(\log \log n)}$ time for central-radicalgroups, and in polynomial time for several prominent subclasses ofcentral-radical groups. We also solve GpI in $n^{O(\log\log n)}$ time forgroups whose solvable normal subgroups are elementary abelian but notnecessarily central. As far as we are aware, this is the first time there havebeen worst-case guarantees on a $n^{o(\log n)}$-time algorithm that tacklesboth aspects of GpI---actions and cohomology---simultaneously.